package com.dmall.graph.tree;

import com.dmall.graph.Graph;
import com.dmall.graph.WeightedEdge;
import com.dmall.graph.WeightedGraph;
import com.dmall.graph.dfs.app.ConnectedComponent;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Kruskal 算法
 * 改算法算是一种贪心的算法
 * @author: xiao1.wang
 * @date: 2022/8/4 22:44
 */
public class Kruskal {

    private WeightedGraph G;
    private List<WeightedEdge> mst;

    public Kruskal(WeightedGraph G) {
        this.G = G;
        this.mst = new ArrayList<>(G.V() - 1);

        ConnectedComponent cc = new ConnectedComponent(G);
        if (cc.count() > 1) {
            return;
        }

        List<WeightedEdge> edges = new ArrayList<>(G.E());
        for (int v = 0; v < G.V(); v++) {
            for (int w : G.adj(v)) {
                if (v < w) {
                    edges.add(new WeightedEdge(v, w, G.getWeight(v, w)));
                }
            }
        }
        Collections.sort(edges);
        UF uf = new UF(G.V());
        for (WeightedEdge edge : edges) {
            if (!uf.isConnected(edge.getV(), edge.getW())) {
                mst.add(edge);
                uf.unionElements(edge.getV(), edge.getW());
            }
        }
    }

    public List<WeightedEdge> result() {
        return mst;
    }

    public static void main(String[] args) {
        String filename = Kruskal.class.getClassLoader().getResource("wg.txt").getPath();
        WeightedGraph g = new WeightedGraph(filename);
        Kruskal kruskal = new Kruskal(g);
        System.out.println(kruskal.result());
    }
}
